#include <vector>
#include <stack>
using namespace std;
/*
 * @lc app=leetcode.cn id=42 lang=cpp
 *
 * [42] 接雨水
 */

// @lc code=start
class Solution {
public:
    // 采用DP
    // int trap(vector<int>& height) {
    //     vector<int> left_max(height.size(), 0), right_max(height.size(), 0);
    //     left_max[0] = height[0]; right_max[height.size() -1] = height.back();
    //     // 
    //     for (int i = 1; i < height.size(); i++) left_max[i] = max(left_max[i - 1], height[i]);
    //     for (int i = height.size() - 2; i >= 0; i--) right_max[i] = max(right_max[i + 1], height[i]);
    //     // 
    //     int res = 0;
    //     for (int i = 0; i < height.size(); i++) {
    //         res += min(left_max[i], right_max[i]) - height[i];
    //     }
    //     return res;
    // }

    // 单调栈
    // int trap(vector<int>& height) {
    //     stack<int> single; int res = 0;
    //     for (int i = 0; i < height.size(); i++) {
    //         while (!single.empty() && height[single.top()] < height[i]) {
    //            int x = height[single.top()]; single.pop();
    //            if (!single.empty()) {
    //                res += (min(height[single.top()], height[i]) - x) * (i - single.top() - 1);
    //            }
    //         }
    //         single.push(i);
    //     }
    //     return res;
    // }

    // 双指针
    int trap(vector<int>& height) {
        int l = 0, r = height.size() - 1, res = 0, left_max = 0, right_max = 0;
        while (l < r) {
            left_max = max(left_max, height[l]);
            right_max = max(right_max, height[r]);
            if (left_max < right_max) {
                res += left_max - height[l];
                l++;
            } else {
                res += right_max - height[r];
                r--;
            }
        }
        return res;
    }

};
// @lc code=end

